package violentRecursion;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @className: LeetCode_198
 * @Description: 打家劫舍
 * @author: kunkun
 * @date: 2025/3/12 23:30
 */
public class LeetCode_198 {

    public int rob(int[] nums) {
//        return solution_1(nums,nums.length-1);
//        int[] values = new int[nums.length];
//        return solution_2(nums, nums.length-1,  values);
        return solution_3(nums);
    }

    @Test
    public void test(){
        System.out.println(rob(new int[]{1,2,3,1}));
    }

    //暴力递归
    private int solution_1(int[] nums, int i) {
        if (i==0){
            return nums[0];
        }
        if (i==1){
            return Math.max(nums[0],nums[1]);
        }
        int v1 = solution_1(nums,i-2)+nums[i];
        int v2 = solution_1(nums,i-1);
        return Math.max(v1,v2);
    }

//    记忆表搜索
    private int solution_2(int[] nums,int i, int[]  values){
        if (values[i]!=0){
            return values[i];
        }
        if (i==0){
            return nums[0];
        }
        if (i==1){
            return Math.max(nums[0],nums[1]);
        }
        int v1 = solution_2(nums,i-2,values)+nums[i];
        int v2 = solution_2(nums,i-1,values);
        int result = Math.max(v1,v2);
        values[i]=result;

        return result;
    }

    //动态规划
    private int solution_3(int[] nums){
        int[] values=new int[nums.length];
        //1. 边界值填入
        if (nums.length>=1){
            values[0]=nums[0];
        }
        if (nums.length>=2){
            values[1]=Math.max(nums[1],nums[0]);
        }
        for (int i = 2; i < nums.length; i++) {
            values[i]=Math.max(values[i-2]+nums[i], values[i-1]);
        }
        return values[values.length-1];

    }





}
